“School of Biological Sciences”

Back to Papers Home
Back to Papers of School of Biological Sciences

Paper   IPM / Biological Sciences / 13212
School of Biological Sciences
  Title:   Tag SNP Selection Via A Genetic Algorithm
  Author(s): 
1.  G. Mahdevar.
2.  J. Zahiri.
3.  M. Sadeghi.
4.  A. Nowzari-Dalini.
5.  H. Ahrabian.
  Status:   Published
  Journal: Biomed Inform
  No.:  5
  Vol.:  43
  Year:  2010
  Pages:   800-804
  Supported by:  IPM
  Abstract:
Single Nucleotide Polymorphisms (SNPs) provide valuable information on human evolutionary history and may lead us to identify genetic variants responsible for human complex diseases. Unfortunately, molecular haplotyping methods are costly, laborious, and time consuming; therefore, algorithms for constructing full haplotype patterns from small available data through computational methods, Tag SNP selection problem, are convenient and attractive. This problem is proved to be an NP-hard problem, so heuristic methods may be useful. In this paper we present a heuristic method based on genetic algorithm to find reasonable solution within acceptable time. The algorithm was tested on a variety of simulated and experimental data. In comparison with the exact algorithm, based on brute force approach, results show that our method can obtain optimal solutions in almost all cases and runs much faster than exact algorithm when the number of SNP sites is large. Our software is available upon request to the corresponding author.

Download TeX format
back to top
scroll left or right